package java学习.代码随想录.动态规划;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/9/3 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 买卖股票的最佳时机III {
    /**
     * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
     *
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
     *
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     *
     * 1. 最多两笔交易： 不买、一笔、两笔
     *  0  不操作
     *  1  第一次买入
     *  2  第一次卖出
     *  3  第二次买入
     *  4  第二次卖出
     *
     *  第i天 第一次买入      之前就买入了第一次（持有状态）    之前没买入，现在买入
          dp[i][1]  =  Math.max(  dp[i-1][1],              dp[i-1][0]-prices[i]);

        第i天 第一次卖出          之前就卖出了            之前第一次 买入 后 卖出
         dp[i][2] = Math.max(dp[i-1][2],          dp[i-1][1]+prices[i]);

        第i天 第2次买入           之前就第2次买入了            第一次卖出后 现在开始买入
         dp[i][3] = Math.max(dp[i-1][3],          dp[i-1][2]-prices[i]);

        第i天 第二次卖出         之前就卖出了              第二次买入后 现在卖出
         dp[i][4] = Math.max(dp[i-1][4],          dp[i-1][3] +prices[i]);
     *
     */
    public static  int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][5];

        dp[0][0] = 0;
//        一开始买入 就亏
        dp[0][1] = -prices[0];
//        一开始卖出没利润
        dp[0][2] = 0;
        dp[0][3] = -prices[0];

        dp[0][4] = 0;

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <=2; j++) {
                dp[i][2*j-1] = Math.max(dp[i-1][2*j-1],dp[i-1][2*(j-1)]-prices[i]);
                dp[i][2*j] = Math.max(dp[i-1][2*j],dp[i-1][2*j-1]+prices[i]);
            }
//    1   2    3     4     5
//  1 2  3 4  5 6
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);

            dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);

            dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3] +prices[i]);

        }
        for (int i = 0; i < n; i++) {
            System.out.println(dp[i][0] +"   "+ dp[i][1]+"   "+ dp[i][2]+"   "+ dp[i][3]+"   "+ dp[i][4]);
        }
        return dp[n-1][4];
    }

//    dp[天数][当前是否持股][卖出的次数]
    public static  int maxProfit2(int[] prices) {
        int n = prices.length;
        int[][][] dp = new int[n][2][3];

        dp[0][0][0] = 0;
//        第一次买入
        dp[0][1][0] = -prices[0];
//        第一次卖出
        dp[0][0][1] = 0;

//        第二次买入
        dp[0][1][1] = -prices[0];
//        第二次卖出
        dp[0][0][2] = 0;
//      第3次买入 不存在
//        dp[0][1][2] = -prices[0];
        for (int i = 1; i < n; i++) {

//          i天未持股 卖出第0次
            dp[i][0][0] = 0;

//          i天 持股, 第1次买入
            dp[i][1][0] = Math.max(dp[i-1][1][0], dp[i-1][0][0] -prices[i] );

//          i天未持股 卖出第1次
            dp[i][0][1] = Math.max(dp[i-1][0][1],dp[i-1][1][0] + prices[i]);


//          i天 持股，第2次买入
            dp[i][1][1] = Math.max(dp[i-1][1][1], dp[i-1][0][1] -prices[i]);

//          i天未持股，卖出第2次
            dp[i][0][2] = Math.max(dp[i-1][0][2], dp[i-1][1][1] + prices[i]);

//          i天持股  第3次买入 不存在 最高2次买入卖出
//            dp[i][1][2] = Math.max(dp[i-1][1][2],dp[i-1][0][1] -prices[i]);

        }
        int result1 = Math.max(dp[n-1][1][0],dp[n-1][0][1]);

        int result2 = Math.max(dp[n-1][1][1],dp[n-1][0][2]);
        return Math.max(result1,result2);
    }
    public static void main(String[] args) {
//        prices = [3,3,5,0,0,3,1,4] 输出：6
        int [] test = {3,3,5,0,0,3,1,4};
        System.out.println(maxProfit(test));
        System.out.println(maxProfit2(test));
    }
}
